#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }

    struct ListNode* head = NULL, * tail = NULL;
    struct ListNode* n1 = list1, * n2 = list2;
    if (n1->val < n2->val)
    {
        head = tail = n1;
        n1 = n1->next;
    }
    else
    {
        head = tail = n2;
        n2 = n2->next;
    }

    while (n1 && n2)
    {
        if (n1->val < n2->val)
        {
            tail->next = n1;
            n1 = n1->next;
        }
        else
        {
            tail->next = n2;
            n2 = n2->next;
        }
        tail = tail->next;
    }
    if (n1)
        tail->next = n1;
    else
        tail->next = n2;

    return head;
}